class Node:
    def __init__(self):
        self.data = None
        self.next = None
        self.prev = None


class Link:
    def __init__(self,data=()):
        self.head = Node()
        self.tail = self.head
        self.length = 0
        for d in data:
            self.append(d)

    def __find__node__by__pos(self,pos):

        """
                    find the node with the given position.
                    +------+      +-------+      +------+
                    | head |--->  | data  | ---> | data |
                    +------+      +-------+      +------+
                :param pos:
                :return:
                Note: the position will be started with the head node.
                """
        try:
            assert pos <= len(self) - 1
        except AssertionError:
            raise IndexError

        node_ptr = self.head
        while pos:
            node_ptr = node_ptr.next
            pos -= 1
        return node_ptr

    def __remove__node__by__pos(self,pos):
        """
                remove the node with specified position
                :param pos:
                :return: the deleted node.
                """
        try:
            assert pos <= len(self)-1
        except AssertionError:
            raise IndexError

        node = self.__find__node__by__pos(pos).next
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        if next_node:
            next_node.prev = prev_node
        if node == self.tail:
            self.tail = prev_node

        return node

    def append(self,data):
        node = Node()
        node.data = data
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
        self.length += 1

    def pop(self,i=-1):
        if i == -1:
            if self.head == self.tail:
                raise IndexError

            node = self.tail
            self.tail = node.prev
            self.tail.next = None
            self.length -= 1
            return node.data
        else:
            node = self.__remove__node__by__pos(i)
            return node.data

    def insert(self,i,data):
        try:
            assert i <= len(self) - 1
        except AssertionError:
            raise IndexError

        node_ptr = self.head
        while i:
            node_ptr = node_ptr.next
            i -= 1

        third_node = node_ptr.next
        node = Node()
        node.data = data

        node.next = third_node
        third_node.prev = node

        node_ptr.next = node
        node.prev = node_ptr
        self.length += 1

    def remove(self,i):
        self.__remove__node__by__pos(i)
        self.length -= 1

    def extend(self,iterable):
        for d in iterable:
            self.append(d)

    def __len__(self):
        return self.length

    def __iter__(self):
        return LinkIterator(self)

    def __setitem__(self, key, value):
        try:
            assert key <= len(self) - 1
        except AssertionError:
            raise IndexError

        node = self.__find__node__by__pos(key)
        node.next.data = value

    def __getitem__(self,item):
        try:
            assert item <= len(self) - 1
        except AssertionError:
            raise IndexError

        node_ptr = self.head.next
        while item:
            node_ptr= node_ptr.next
            item -= 1
        return node_ptr.data

    def __contains__(self, item):
        for d in self:
            if d == item:
                return True
        return False

    def __str__(self):
        return str([i for i in self])

    def __add__(self, other):
        for i in other:
            self.append(i)
        return self


class LinkIterator:
    def __init__(self,link):
        self._node_ptr = link.head

    def __next__(self):
        self._node_ptr = self._node_ptr.next
        if self._node_ptr is None:
            raise StopIteration

        data = self._node_ptr.data
        return data


list = Link
x = list((1,2,3,4))
f = list((7,8,9))
a,b,c,d = x
print(a,b,c,d)
print(x)
x.insert(2,8)
print(x.pop(2))
x.__setitem__(3,8)
print(x.pop(3))


l = x+f
print(l)
